With the proliferation of processing power and electronic communication bandwidth, an explosion of data is being generated and transmitted by a multitude of sources. This data is collected and stored for analysis for a wide variety of applications. One such area where this has seen particular explosive growth is in electronic trading of financial products.
At one time, there were only open-outcry exchanges where brokers and traders, or more specifically buyers and sellers, would come together to trade in person. More recently, electronic exchanges that process automatic and electronic matching of bids and offers have been introduced. Thus, trading methods have evolved from a manually intensive process to a technology enabled, electronic platform.
Electronic trading is generally based on centralized (host) computers, one or more computer networks, and exchange participant (client) computers. In general, the host exchange includes one or more centralized computers. The operations of the host exchange typically include order matching, maintaining order books and positions, price information, and managing and updating the database for the trading day as well as nightly batch runs. The host exchange also is equipped with external interfaces that maintain contact with quote vendors and other price information systems.
Using client devices, market participants link to the host exchange through one or more networks. A network is a group of two or more computers or devices linked together. There are many types of wired and wireless networks, such as for example local area networks and wide area networks. Networks can also be characterized by topology, protocol, and architecture. For example, some market participants may link to the host through a direct connection such as an Integrated Services Digital Network (ISDN) or T1. Some participants link to the host exchange through direct connections and through other common network components such as high-speed servers, routers, and gateways. There are many different types of networks and combinations of network types that can link traders to the host exchange. The Internet can be used to establish a connection between the client device and the host exchange.
The Internet is a global network of computers. Network servers support hypertext capabilities that permit the Internet to link together webs of documents. User interfaces such as Graphical User Interfaces (GUI) are typically used to navigate the Internet to retrieve relevant documents. Uniform Resource Locators (URLs) are used to identify specific web sites and web pages on the Internet. URLs also identify the address of the document to be retrieved from a network server.
To transmit digitized information in a reliable way, the Internet uses a packet-switching design. Packet switching breaks up blocks of digitized information into smaller pieces called packets. These packets are transmitted through the network, usually by different routes, and are then reassembled at their destination. See, e.g., Len Kleinrock, “Information Flow in Large Communications Nets”, RLE Quarterly Progress Report (1960); Len Kleinrock, Communication Nets (1964). See also Paul Baren, “On Distributed Communications Networks”, IEEE Transactions on Systems (March 1964).
The original packet switching employed by the Internet was referred to as the Transmission Control Protocol/Internet Protocol (TCP/IP). The Transmission Control Protocol (TCP) packetizes information and reassembles the information upon arrival. The Internet Protocol (IP) routes packets by encasing the packets between networks. See, e.g., Robert Kahn and Vincent Cerf, “A Protocol for Packet Network Intercommunication”, IEEE Transactions on Communications Technology (May 1974). There are many additional protocols used for relaying Internet traffic.
More recent packet switching employed by the Internet includes the User Datagram Protocol/Internet Protocol (UDP/IP). Host exchanges frequently transmit information about the trading market to client devices using the UDP/IP protocol. UDP/IP uses a simple transmission model without implicit handshaking dialogues for providing reliability, ordering or data integrity. UDP provides an unreliable service and datagrams may arrive out of order, appear duplicated or go missing without notice; thus, UDP assumes that error checking and correction is either not necessary or performed in the application, avoiding the overhead of such processing at the network interface level. Time-sensitive applications often use UDP because dropping packets is preferable to waiting for delayed packets, which may not be an option in a real-time system. There are many other communication protocols TCP/IP and UDP/IP that can be used to transit or receive data over a network.
TCP/IP and UDP/IP are examples of the communication protocols that can be classified by the Open Systems Interconnection (OSI) model. The OSI model is a prescription of characterizing and standardizing the functions of a communication system in terms of layers. Similar communication functions are grouped into logical layers, with a layer serving the layer above it, and being served by the layer below it. The lowest layer of the OSI model is the Physical Layer, also known as “Layer 1”, and commonly abbreviated to “PHY”. The physical layer defines the electrical and physical specifications between a computer device and a transmission medium, such as copper or optical fiber cable. Examples of physical layers include DSL, ISDN, Ethernet physical layer (10BASE-T, 10BASE2, 100BASE-TX, 1000BASE-T, and other varieties), Infiniband, T1, and the like.
Above the physical layer is the data link layer, also known as “Layer 2”. The data link layer provides the functional and procedural means to transfer data between network entities and detect and correct errors that may occur in the physical layer. Examples of data link layers include ARP, ATM, Ethernet, Frame Relay, 802.11, Infiniband, Token Ring, and the like. For both TCP/IP and UDP/IP, the data link layer is responsible for encapsulation of IP packets into frames, frame synchronization, error detection and handling, and addressing via media access control (MAC), among others.
Above the data link layer is the network layer, also known as ‘Layer 3’. This layer is concerned with actually getting data from one computer to another, even if the computer is remote or on different network. Functions of the network layer include connectionless communication, host addressing, and messaging forwarding. Example network layer protocols include IPv4 and IPv6, ICMP, IGMP, PIM-SM and PIM-DM, Infiniband, IPX, and the like. For both TCP/IP and UDP/IP, the Internet Protocol, or “IP”, is the Layer 3 implementation used to route packets through one or many networks.
Above the network layer is the transport layer, also known as ‘Layer 4’. The transport layer provides end-to-end communication services such as connection-oriented data stream support, reliability, flow control, congestion avoidance, byte orientation, and multiplexing. Examples of transport layers include TCP, UDP, RDP, IL, Infiniband, ATP, and the like.
The Internet is an example of an implementation of the OSI model. There are many other examples of networks, including personal networks, local area networks, home networks, storage area networks, campus networks, backbone networks, metropolitan area networks, wide area networks, virtual private networks, and the like. Usage, trust level, and access rights differ between these different types of networks.
A subset of data collection problems deals with data generated from a variety of sources, and transmitted at a very high rate on a computer network using a communication protocol such as for example UDP/IP. Any solution that captures and persists this data for use is subject to some basic requirements. Persists refers to the characteristic of configurations of information in a program or machine that outlives the process that created it. Without persistence, this information would only exist in random access memory (RAM), and would be lost when this RAM loses power, such as a computer shutdown. Persistence is achieved in practice by storing the information as data in non-volatile storage such as a hard drive or flash memory.
First, the persisted must be a one-for-one snapshot of all of the data that was broadcasted from the source. If data is transmitted, but not persisted, this is known as a ‘gap’ or a ‘drop’. Many categories of usage break down if the persisted data contains gaps. Since transmitted data is usually not repeatable, the data capture solution must guarantee that all transmitted packets will be captured and persisted.
Second, under normal network load conditions, users must be able to access persisted data even as new transmitted data is being captured and persisted. Inability to access persisted data would handicap many business processes because the business processes will be unable to respond to changing conditions in their environment. For example, the act of detecting and responding to packet loss in a network would be severely hampered if the network administrator were unable to access the persisted network data until the end of the business day. User access has the potential to interrupt the process of persisting data, as the two activities are both contending for the same finite set of computer resources. This potential becomes more likely as network traffic load increases. As network load increases towards capture and persistence capacity, existing systems will allow capture rate to degrade as a result of increased user access, leading to data gaps.
Existing systems that attempt to solve this problem share a common design. The typical approach is to use a hardware device referred to as a passive network tap that provides a way to access data flowing across a computer network. The passive network tap duplicates a stream of packets and routes the stream of packets to a network communication protocol capture card installed in a packet capture appliance. The network communication protocol capture card hands incoming packets to a process on the system, which persists them to a storage medium. The typical system implementation uses a computer running an operating system and a magnetic or flash disk drive for storage.
Existing systems manage the reading and writing of information on storage through a straightforward algorithmic process. Read refers to a user accessing stored information while write refers to storing the information. One example is ‘round robin’, where a scheduler selects a read or write pointed to by a counter from a list, after which the counter is incremented and if the end is reached, the scheduler returns to the beginning of the list. Another example is ‘first-in-first-out’, where a scheduler stores read and writes in a queue, with the first read or write to be added to the queue the first read or write to be acted upon, with processing proceeds sequentially in the same order.
The ability of existing solutions to meet the criteria outlined above rests with ensuring a high and consistent rate of persisting (writing) incoming data to the storage medium under conditions of load consisting of both transmission persistence and user access. Under typical loads consisting of mixtures of read and write requests, storage media exhibit a high variability in the latency of individual write requests and a lower overall total performance. For magnetic media, this is due to the seek-time latency as the read-write heads traverse between the storage cylinders. For flash media, this is to what has been termed the ‘bathtub effect’: high numbers for pure reads and writes but much lower ones for mixed workloads.
This variability in the effective write performance of the storage medium degrades the ability to maintain a high and consistent write performance. This in turn creates backpressure on the rest of the system. If this backpressure reaches the network communication protocol capture card, the card has no choice but to drop incoming packets due to internal memory buffer overflow. This happens because a capture solution is passive in nature, meaning that the presence of the capture solution on the network is unknown to other network devices. As a result, the system cannot request that packets be retransmitted if the network communication protocol capture card cannot keep up with the packet rate.
Existing solutions use a number of mechanisms to attempt to prevent this ‘backpressure’ (the build up of data that occurs when buffers are full and incapable of receiving more data) from reaching the network communication protocol capture card. Such mechanisms use a region of memory—either on the card itself, inside the process or inside the operating system (known as the page cache)—to create one or more buffers between the network communication protocol, capture card, and the storage medium. While these mechanisms can smooth out the variability in the write performance of the storage medium, when all the buffers fill the backpressure inevitably reaches the network communication protocol capture card, forcing it to drop packets. Such mechanisms also have the disadvantage of taking memory resources away from the rest of the system.